#define Infinite 65535
#define VERTEXMAXNUM 3001
typedef struct ENode ElementType;
struct ENode{
	int V;
	int W;
	int Weight;
};
typedef struct HNode* MinHeap;
typedef struct HNode* Heap;
struct HNode{
	int Size;
	ElementType HeapMatrix[VERTEXMAXNUM];
};
Heap CreateHeap(int M)
{
	Heap H=(Heap)malloc(sizeof(struct HNode));
	H->Size=M;
	H->HeapMatrix[0].Weight=-1;//哨兵
	int i=1;
	for(i=1;i<=M;i++){
	    scanf("%d %d %d",&(H->HeapMatrix[i].V),&(H->HeapMatrix[i].W),&(H->HeapMatrix[i].Weight));
	}
	return H;
}
void PercDown(Heap H,int V)
{
	int T=H->HeapMatrix[V].Weight;
	ElementType TNode=H->HeapMatrix[V];
	int parent,child;
	for(parent=V;parent*2<=H->Size;parent=child){
	    child=2*parent;
	    if(child!=H->Size&&((H->HeapMatrix[child].Weight)>(H->HeapMatrix[child+1].Weight))){
	        child++;
	    }
	    if(H->HeapMatrix[child].Weight<T){
	        H->HeapMatrix[parent]=H->HeapMatrix[child];
	    }else{
	        break;
	    }
	}
	H->HeapMatrix[parent]=TNode;
}
void BuildMinheap(Heap H)
{
	 int i=H->Size/2;
	 for(;i>=1;i--){
	    PercDown(H,i);
	 }
}
ElementType DeleteMinHeap(MinHeap H)
{
	ElementType Node={.Weight=-1};
	if(H->Size==0){
	    return Node;
	}
	Node=H->HeapMatrix[1];
	H->HeapMatrix[1]=H->HeapMatrix[H->Size--];
	PercDown(H,1);
	return Node;
}    